{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6249c5aa",
   "metadata": {
    "origin_pos": 0
   },
   "source": [
    "# Introduction\n",
    ":label:`chap_introduction`\n",
    "\n",
    "Until recently, nearly every computer program\n",
    "that you might have interacted with during\n",
    "an ordinary day\n",
    "was coded up as a rigid set of rules\n",
    "specifying precisely how it should behave.\n",
    "Say that we wanted to write an application\n",
    "to manage an e-commerce platform.\n",
    "After huddling around a whiteboard\n",
    "for a few hours to ponder the problem,\n",
    "we might settle on the broad strokes\n",
    "of a working solution, for example:\n",
    "(i) users interact with the application through an interface\n",
    "running in a web browser or mobile application;\n",
    "(ii) our application interacts with a commercial-grade database engine\n",
    "to keep track of each user's state and maintain records\n",
    "of historical transactions;\n",
    "and (iii) at the heart of our application,\n",
    "the *business logic* (you might say, the *brains*) of our application\n",
    "spells out a set of rules that map every conceivable circumstance\n",
    "to the corresponding action that our program should take.\n",
    "\n",
    "To build the brains of our application,\n",
    "we might enumerate all the common events\n",
    "that our program should handle.\n",
    "For example, whenever a customer clicks\n",
    "to add an item to their shopping cart,\n",
    "our program should add an entry\n",
    "to the shopping cart database table,\n",
    "associating that user's ID\n",
    "with the requested product's ID.\n",
    "We might then attempt to step through\n",
    "every possible corner case,\n",
    "testing the appropriateness of our rules\n",
    "and making any necessary modifications.\n",
    "What happens if a user\n",
    "initiates a purchase with an empty cart?\n",
    "While few developers ever get it\n",
    "completely right the first time\n",
    "(it might take some test runs to work out the kinks),\n",
    "for the most part we can write such programs\n",
    "and confidently launch them\n",
    "*before* ever seeing a real customer.\n",
    "Our ability to manually design automated systems\n",
    "that drive functioning products and systems,\n",
    "often in novel situations,\n",
    "is a remarkable cognitive feat.\n",
    "And when you are able to devise solutions\n",
    "that work $100\\%$ of the time,\n",
    "you typically should not be\n",
    "worrying about machine learning.\n",
    "\n",
    "Fortunately for the growing community\n",
    "of machine learning scientists,\n",
    "many tasks that we would like to automate\n",
    "do not bend so easily to human ingenuity.\n",
    "Imagine huddling around the whiteboard\n",
    "with the smartest minds you know,\n",
    "but this time you are tackling\n",
    "one of the following problems:\n",
    "\n",
    "* Write a program that predicts tomorrow's weather given geographic information, satellite images, and a trailing window of past weather.\n",
    "* Write a program that takes in a factoid question, expressed in free-form text, and  answers it correctly.\n",
    "* Write a program that, given an image, identifies every person depicted in it and draws outlines around each.\n",
    "* Write a program that presents users with products that they are likely to enjoy but unlikely, in the natural course of browsing, to encounter.\n",
    "\n",
    "For these problems,\n",
    "even elite programmers would struggle\n",
    "to code up solutions from scratch.\n",
    "The reasons can vary.\n",
    "Sometimes the program that we are looking for\n",
    "follows a pattern that changes over time,\n",
    "so there is no fixed right answer!\n",
    "In such cases, any successful solution\n",
    "must adapt gracefully to a changing world.\n",
    "At other times, the relationship (say between pixels,\n",
    "and abstract categories) may be too complicated,\n",
    "requiring thousands or millions of computations\n",
    "and following unknown principles.\n",
    "In the case of image recognition,\n",
    "the precise steps required to perform the task\n",
    "lie beyond our conscious understanding,\n",
    "even though our subconscious cognitive processes\n",
    "execute the task effortlessly.\n",
    "\n",
    "\n",
    "*Machine learning* is the study of algorithms\n",
    "that can learn from experience.\n",
    "As a machine learning algorithm accumulates more experience,\n",
    "typically in the form of observational data\n",
    "or interactions with an environment,\n",
    "its performance improves.\n",
    "Contrast this with our deterministic e-commerce platform,\n",
    "which follows the same business logic,\n",
    "no matter how much experience accrues,\n",
    "until the developers themselves learn and decide\n",
    "that it is time to update the software.\n",
    "In this book, we will teach you\n",
    "the fundamentals of machine learning,\n",
    "focusing in particular on *deep learning*,\n",
    "a powerful set of techniques\n",
    "driving innovations in areas as diverse as computer vision,\n",
    "natural language processing, healthcare, and genomics.\n",
    "\n",
    "## A Motivating Example\n",
    "\n",
    "Before beginning writing, the authors of this book,\n",
    "like much of the work force, had to become caffeinated.\n",
    "We hopped in the car and started driving.\n",
    "Using an iPhone, Alex called out \"Hey Siri\",\n",
    "awakening the phone's voice recognition system.\n",
    "Then Mu commanded \"directions to Blue Bottle coffee shop\".\n",
    "The phone quickly displayed the transcription of his command.\n",
    "It also recognized that we were asking for directions\n",
    "and launched the Maps application (app)\n",
    "to fulfill our request.\n",
    "Once launched, the Maps app identified a number of routes.\n",
    "Next to each route, the phone displayed a predicted transit time.\n",
    "While this story was fabricated for pedagogical convenience,\n",
    "it demonstrates that in the span of just a few seconds,\n",
    "our everyday interactions with a smart phone\n",
    "can engage several machine learning models.\n",
    "\n",
    "\n",
    "Imagine just writing a program to respond to a *wake word*\n",
    "such as \"Alexa\", \"OK Google\", and \"Hey Siri\".\n",
    "Try coding it up in a room by yourself\n",
    "with nothing but a computer and a code editor,\n",
    "as illustrated in :numref:`fig_wake_word`.\n",
    "How would you write such a program from first principles?\n",
    "Think about it... the problem is hard.\n",
    "Every second, the microphone will collect roughly\n",
    "44,000 samples.\n",
    "Each sample is a measurement of the amplitude of the sound wave.\n",
    "What rule could map reliably from a snippet of raw audio to confident predictions\n",
    "$\\{\\textrm{yes}, \\textrm{no}\\}$\n",
    "about whether the snippet contains the wake word?\n",
    "If you are stuck, do not worry.\n",
    "We do not know how to write such a program from scratch either.\n",
    "That is why we use machine learning.\n",
    "\n",
    "![Identify a wake word.](../img/wake-word.svg)\n",
    ":label:`fig_wake_word`\n",
    "\n",
    "\n",
    "Here is the trick.\n",
    "Often, even when we do not know how to tell a computer\n",
    "explicitly how to map from inputs to outputs,\n",
    "we are nonetheless capable of performing the cognitive feat ourselves.\n",
    "In other words, even if you do not know\n",
    "how to program a computer to recognize the word \"Alexa\",\n",
    "you yourself are able to recognize it.\n",
    "Armed with this ability, we can collect a huge *dataset*\n",
    "containing examples of audio snippets and associated labels,\n",
    "indicating which snippets contain the wake word.\n",
    "In the currently dominant approach to machine learning,\n",
    "we do not attempt to design a system\n",
    "*explicitly* to recognize wake words.\n",
    "Instead, we define a flexible program\n",
    "whose behavior is determined by a number of *parameters*.\n",
    "Then we use the dataset to determine the best possible parameter values,\n",
    "i.e., those that improve the performance of our program\n",
    "with respect to a chosen performance measure.\n",
    "\n",
    "You can think of the parameters as knobs that we can turn,\n",
    "manipulating the behavior of the program.\n",
    "Once the parameters are fixed, we call the program a *model*.\n",
    "The set of all distinct programs (input--output mappings)\n",
    "that we can produce just by manipulating the parameters\n",
    "is called a *family* of models.\n",
    "And the \"meta-program\" that uses our dataset\n",
    "to choose the parameters is called a *learning algorithm*.\n",
    "\n",
    "Before we can go ahead and engage the learning algorithm,\n",
    "we have to define the problem precisely,\n",
    "pinning down the exact nature of the inputs and outputs,\n",
    "and choosing an appropriate model family.\n",
    "In this case,\n",
    "our model receives a snippet of audio as *input*,\n",
    "and the model\n",
    "generates a selection among\n",
    "$\\{\\textrm{yes}, \\textrm{no}\\}$ as *output*.\n",
    "If all goes according to plan\n",
    "the model's guesses will\n",
    "typically be correct as to\n",
    "whether the snippet contains the wake word.\n",
    "\n",
    "If we choose the right family of models,\n",
    "there should exist one setting of the knobs\n",
    "such that the model fires \"yes\" every time it hears the word \"Alexa\".\n",
    "Because the exact choice of the wake word is arbitrary,\n",
    "we will probably need a model family sufficiently rich that,\n",
    "via another setting of the knobs, it could fire \"yes\"\n",
    "only upon hearing the word \"Apricot\".\n",
    "We expect that the same model family should be suitable\n",
    "for \"Alexa\" recognition and \"Apricot\" recognition\n",
    "because they seem, intuitively, to be similar tasks.\n",
    "However, we might need a different family of models entirely\n",
    "if we want to deal with fundamentally different inputs or outputs,\n",
    "say if we wanted to map from images to captions,\n",
    "or from English sentences to Chinese sentences.\n",
    "\n",
    "As you might guess, if we just set all of the knobs randomly,\n",
    "it is unlikely that our model will recognize \"Alexa\",\n",
    "\"Apricot\", or any other English word.\n",
    "In machine learning,\n",
    "the *learning* is the process\n",
    "by which we discover the right setting of the knobs\n",
    "for coercing the desired behavior from our model.\n",
    "In other words,\n",
    "we *train* our model with data.\n",
    "As shown in :numref:`fig_ml_loop`, the training process usually looks like the following:\n",
    "\n",
    "1. Start off with a randomly initialized model that cannot do anything useful.\n",
    "1. Grab some of your data (e.g., audio snippets and corresponding $\\{\\textrm{yes}, \\textrm{no}\\}$ labels).\n",
    "1. Tweak the knobs to make the model perform better as assessed on those examples.\n",
    "1. Repeat Steps 2 and 3 until the model is awesome.\n",
    "\n",
    "![A typical training process.](../img/ml-loop.svg)\n",
    ":label:`fig_ml_loop`\n",
    "\n",
    "To summarize, rather than code up a wake word recognizer,\n",
    "we code up a program that can *learn* to recognize wake words,\n",
    "if presented with a large labeled dataset.\n",
    "You can think of this act of determining a program's behavior\n",
    "by presenting it with a dataset as *programming with data*.\n",
    "That is to say, we can \"program\" a cat detector\n",
    "by providing our machine learning system\n",
    "with many examples of cats and dogs.\n",
    "This way the detector will eventually learn to emit\n",
    "a very large positive number if it is a cat,\n",
    "a very large negative number if it is a dog,\n",
    "and something closer to zero if it is not sure.\n",
    "This barely scratches the surface of what machine learning can do.\n",
    "Deep learning, which we will explain in greater detail later,\n",
    "is just one among many popular methods\n",
    "for solving machine learning problems.\n",
    "\n",
    "\n",
    "## Key Components\n",
    "\n",
    "In our wake word example, we described a dataset\n",
    "consisting of audio snippets and binary labels,\n",
    "and we gave a hand-wavy sense of how we might train\n",
    "a model to approximate a mapping from snippets to classifications.\n",
    "This sort of problem,\n",
    "where we try to predict a designated unknown label\n",
    "based on known inputs\n",
    "given a dataset consisting of examples\n",
    "for which the labels are known,\n",
    "is called *supervised learning*.\n",
    "This is just one among many kinds of machine learning problems.\n",
    "Before we explore other varieties,\n",
    "we would like to shed more light\n",
    "on some core components that will follow us around,\n",
    "no matter what kind of machine learning problem we tackle:\n",
    "\n",
    "1. The *data* that we can learn from.\n",
    "1. A *model* of how to transform the data.\n",
    "1. An *objective function* that quantifies how well (or badly) the model is doing.\n",
    "1. An *algorithm* to adjust the model's parameters to optimize the objective function.\n",
    "\n",
    "### Data\n",
    "\n",
    "It might go without saying that you cannot do data science without data.\n",
    "We could lose hundreds of pages pondering what precisely data *is*,\n",
    "but for now, we will focus on the key properties\n",
    "of the datasets that we will be concerned with.\n",
    "Generally, we are concerned with a collection of examples.\n",
    "In order to work with data usefully, we typically\n",
    "need to come up with a suitable numerical representation.\n",
    "Each *example* (or *data point*, *data instance*, *sample*)\n",
    "typically consists of a set of attributes\n",
    "called *features* (sometimes called *covariates* or *inputs*),\n",
    "based on which the model must make its predictions.\n",
    "In supervised learning problems,\n",
    "our goal is to predict the value of a special attribute,\n",
    "called the *label* (or *target*),\n",
    "that is not part of the model's input.\n",
    "\n",
    "If we were working with image data,\n",
    "each example might consist of an\n",
    "individual photograph (the features)\n",
    "and a number indicating the category\n",
    "to which the photograph belongs (the label).\n",
    "The photograph would be represented numerically\n",
    "as three grids of numerical values representing\n",
    "the brightness of red, green, and blue light\n",
    "at each pixel location.\n",
    "For example, a $200\\times 200$ pixel color photograph\n",
    "would consist of $200\\times200\\times3=120000$ numerical values.\n",
    "\n",
    "Alternatively, we might work with electronic health record data\n",
    "and tackle the task of predicting the likelihood\n",
    "that a given patient  will survive the next 30 days.\n",
    "Here, our features might consist of a collection\n",
    "of readily available attributes\n",
    "and frequently recorded measurements,\n",
    "including age, vital signs, comorbidities,\n",
    "current medications, and recent procedures.\n",
    "The label available for training would be a binary value\n",
    "indicating whether each patient in the historical data\n",
    "survived within the 30-day window.\n",
    "\n",
    "In such cases, when every example is characterized\n",
    "by the same number of numerical features,\n",
    "we say that the inputs are fixed-length vectors\n",
    "and we call the (constant) length of the vectors\n",
    "the *dimensionality* of the data.\n",
    "As you might imagine, fixed-length inputs can be convenient,\n",
    "giving us one less complication to worry about.\n",
    "However, not all data can easily\n",
    "be represented as *fixed-length* vectors.\n",
    "While we might expect microscope images\n",
    "to come from standard equipment,\n",
    "we cannot expect images mined from the Internet\n",
    "all to have the same resolution or shape.\n",
    "For images, we might consider\n",
    "cropping them to a standard size,\n",
    "but that strategy only gets us so far.\n",
    "We risk losing information in the cropped-out portions.\n",
    "Moreover, text data resists fixed-length\n",
    "representations even more stubbornly.\n",
    "Consider the customer reviews left\n",
    "on e-commerce sites such as Amazon, IMDb, and TripAdvisor.\n",
    "Some are short: \"it stinks!\".\n",
    "Others ramble for pages.\n",
    "One major advantage of deep learning over traditional methods\n",
    "is the comparative grace with which modern models\n",
    "can handle *varying-length* data.\n",
    "\n",
    "Generally, the more data we have, the easier our job becomes.\n",
    "When we have more data, we can train more powerful models\n",
    "and rely less heavily on preconceived assumptions.\n",
    "The regime change from (comparatively) small to big data\n",
    "is a major contributor to the success of modern deep learning.\n",
    "To drive the point home, many of\n",
    "the most exciting models in deep learning\n",
    "do not work without large datasets.\n",
    "Some others might work in the small data regime,\n",
    "but are no better than traditional approaches.\n",
    "\n",
    "Finally, it is not enough to have lots of data\n",
    "and to process it cleverly.\n",
    "We need the *right* data.\n",
    "If the data is full of mistakes,\n",
    "or if the chosen features are not predictive\n",
    "of the target quantity of interest,\n",
    "learning is going to fail.\n",
    "The situation is captured well by the cliché:\n",
    "*garbage in, garbage out*.\n",
    "Moreover, poor predictive performance\n",
    "is not the only potential consequence.\n",
    "In sensitive applications of machine learning,\n",
    "like predictive policing, resume screening,\n",
    "and risk models used for lending,\n",
    "we must be especially alert\n",
    "to the consequences of garbage data.\n",
    "One commonly occurring failure mode concerns datasets\n",
    "where some groups of people are unrepresented\n",
    "in the training data.\n",
    "Imagine applying a skin cancer recognition system\n",
    "that had never seen black skin before.\n",
    "Failure can also occur when the data\n",
    "does not only under-represent some groups\n",
    "but reflects societal prejudices.\n",
    "For example, if past hiring decisions\n",
    "are used to train a predictive model\n",
    "that will be used to screen resumes\n",
    "then machine learning models could inadvertently\n",
    "capture and automate historical injustices.\n",
    "Note that this can all happen without the data scientist\n",
    "actively conspiring, or even being aware.\n",
    "\n",
    "\n",
    "### Models\n",
    "\n",
    "Most machine learning involves transforming the data in some sense.\n",
    "We might want to build a system that ingests photos and predicts smiley-ness.\n",
    "Alternatively,\n",
    "we might want to ingest a set of sensor readings\n",
    "and predict how normal vs. anomalous the readings are.\n",
    "By *model*, we denote the computational machinery for ingesting data\n",
    "of one type,\n",
    "and spitting out predictions of a possibly different type.\n",
    "In particular, we are interested in *statistical models*\n",
    "that can be estimated from data.\n",
    "While simple models are perfectly capable of addressing\n",
    "appropriately simple problems,\n",
    "the problems\n",
    "that we focus on in this book stretch the limits of classical methods.\n",
    "Deep learning is differentiated from classical approaches\n",
    "principally by the set of powerful models that it focuses on.\n",
    "These models consist of many successive transformations of the data\n",
    "that are chained together top to bottom, thus the name *deep learning*.\n",
    "On our way to discussing deep models,\n",
    "we will also discuss some more traditional methods.\n",
    "\n",
    "### Objective Functions\n",
    "\n",
    "Earlier, we introduced machine learning as learning from experience.\n",
    "By *learning* here,\n",
    "we mean improving at some task over time.\n",
    "But who is to say what constitutes an improvement?\n",
    "You might imagine that we could propose updating our model,\n",
    "and some people might disagree on whether our proposal\n",
    "constituted an improvement or not.\n",
    "\n",
    "In order to develop a formal mathematical system of learning machines,\n",
    "we need to have formal measures of how good (or bad) our models are.\n",
    "In machine learning, and optimization more generally,\n",
    "we call these *objective functions*.\n",
    "By convention, we usually define objective functions\n",
    "so that lower is better.\n",
    "This is merely a convention.\n",
    "You can take any function\n",
    "for which higher is better, and turn it into a new function\n",
    "that is qualitatively identical but for which lower is better\n",
    "by flipping the sign.\n",
    "Because we choose lower to be better, these functions are sometimes called\n",
    "*loss functions*.\n",
    "\n",
    "When trying to predict numerical values,\n",
    "the most common loss function is *squared error*,\n",
    "i.e., the square of the difference between\n",
    "the prediction and the ground truth target.\n",
    "For classification, the most common objective\n",
    "is to minimize error rate,\n",
    "i.e., the fraction of examples on which\n",
    "our predictions disagree with the ground truth.\n",
    "Some objectives (e.g., squared error) are easy to optimize,\n",
    "while others (e.g., error rate) are difficult to optimize directly,\n",
    "owing to non-differentiability or other complications.\n",
    "In these cases, it is common instead to optimize a *surrogate objective*.\n",
    "\n",
    "During optimization, we think of the loss\n",
    "as a function of the model's parameters,\n",
    "and treat the training dataset as a constant.\n",
    "We learn\n",
    "the best values of our model's parameters\n",
    "by minimizing the loss incurred on a set\n",
    "consisting of some number of examples collected for training.\n",
    "However, doing well on the training data\n",
    "does not guarantee that we will do well on unseen data.\n",
    "So we will typically want to split the available data into two partitions:\n",
    "the *training dataset* (or *training set*), for learning model parameters;\n",
    "and the *test dataset* (or *test set*), which is held out for evaluation.\n",
    "At the end of the day, we typically report\n",
    "how our models perform on both partitions.\n",
    "You could think of training performance\n",
    "as analogous to the scores that a student achieves\n",
    "on the practice exams used to prepare for some real final exam.\n",
    "Even if the results are encouraging,\n",
    "that does not guarantee success on the final exam.\n",
    "Over the course of studying, the student\n",
    "might begin to memorize the practice questions,\n",
    "appearing to master the topic but faltering\n",
    "when faced with previously unseen questions\n",
    "on the actual final exam.\n",
    "When a model performs well on the training set\n",
    "but fails to generalize to unseen data,\n",
    "we say that it is *overfitting* to the training data.\n",
    "\n",
    "\n",
    "### Optimization Algorithms\n",
    "\n",
    "Once we have got some data source and representation,\n",
    "a model, and a well-defined objective function,\n",
    "we need an algorithm capable of searching\n",
    "for the best possible parameters for minimizing the loss function.\n",
    "Popular optimization algorithms for deep learning\n",
    "are based on an approach called *gradient descent*.\n",
    "In brief, at each step, this method\n",
    "checks to see, for each parameter,\n",
    "how that training set loss would change\n",
    "if you perturbed that parameter by just a small amount.\n",
    "It would then update the parameter\n",
    "in the direction that lowers the loss.\n",
    "\n",
    "\n",
    "## Kinds of Machine Learning Problems\n",
    "\n",
    "The wake word problem in our motivating example\n",
    "is just one among many\n",
    "that machine learning can tackle.\n",
    "To motivate the reader further\n",
    "and provide us with some common language\n",
    "that will follow us throughout the book,\n",
    "we now provide a broad overview of the landscape\n",
    "of machine learning problems.\n",
    "\n",
    "### Supervised Learning\n",
    "\n",
    "Supervised learning describes tasks\n",
    "where we are given a dataset\n",
    "containing both features and labels\n",
    "and \n",
    "asked to produce a model that predicts the labels when\n",
    "given input features.\n",
    "Each feature--label pair is called an example.\n",
    "Sometimes, when the context is clear,\n",
    "we may use the term *examples*\n",
    "to refer to a collection of inputs,\n",
    "even when the corresponding labels are unknown.\n",
    "The supervision comes into play\n",
    "because, for choosing the parameters,\n",
    "we (the supervisors) provide the model\n",
    "with a dataset consisting of labeled examples.\n",
    "In probabilistic terms, we typically are interested in estimating\n",
    "the conditional probability of a label given input features.\n",
    "While it is just one among several paradigms,\n",
    "supervised learning accounts for the majority of successful\n",
    "applications of machine learning in industry.\n",
    "Partly that is because many important tasks\n",
    "can be described crisply as estimating the probability\n",
    "of something unknown given a particular set of available data:\n",
    "\n",
    "* Predict cancer vs. not cancer, given a computer tomography image.\n",
    "* Predict the correct translation in French, given a sentence in English.\n",
    "* Predict the price of a stock next month based on this month's financial reporting data.\n",
    "\n",
    "While all supervised learning problems\n",
    "are captured by the simple description\n",
    "\"predicting the labels given input features\",\n",
    "supervised learning itself can take diverse forms\n",
    "and require tons of modeling decisions,\n",
    "depending on (among other considerations)\n",
    "the type, size, and quantity of the inputs and outputs.\n",
    "For example, we use different models\n",
    "for processing sequences of arbitrary lengths\n",
    "and fixed-length vector representations.\n",
    "We will visit many of these problems\n",
    "in depth throughout this book.\n",
    "\n",
    "Informally, the learning process looks something like the following.\n",
    "First, grab a big collection of examples for which the features are known\n",
    "and select from them a random subset,\n",
    "acquiring the ground truth labels for each.\n",
    "Sometimes these labels might be available data that have already been collected\n",
    "(e.g., did a patient die within the following year?)\n",
    "and other times we might need to employ human annotators to label the data,\n",
    "(e.g., assigning images to categories).\n",
    "Together, these inputs and corresponding labels comprise the training set.\n",
    "We feed the training dataset into a supervised learning algorithm,\n",
    "a function that takes as input a dataset\n",
    "and outputs another function: the learned model.\n",
    "Finally, we can feed previously unseen inputs to the learned model,\n",
    "using its outputs as predictions of the corresponding label.\n",
    "The full process is drawn in :numref:`fig_supervised_learning`.\n",
    "\n",
    "![Supervised learning.](../img/supervised-learning.svg)\n",
    ":label:`fig_supervised_learning`\n",
    "\n",
    "#### Regression\n",
    "\n",
    "Perhaps the simplest supervised learning task\n",
    "to wrap your head around is *regression*.\n",
    "Consider, for example, a set of data harvested\n",
    "from a database of home sales.\n",
    "We might construct a table,\n",
    "in which each row corresponds to a different house,\n",
    "and each column corresponds to some relevant attribute,\n",
    "such as the square footage of a house,\n",
    "the number of bedrooms, the number of bathrooms,\n",
    "and the number of minutes (walking) to the center of town.\n",
    "In this dataset, each example would be a specific house,\n",
    "and the corresponding feature vector would be one row in the table.\n",
    "If you live in New York or San Francisco,\n",
    "and you are not the CEO of Amazon, Google, Microsoft, or Facebook,\n",
    "the (sq. footage, no. of bedrooms, no. of bathrooms, walking distance)\n",
    "feature vector for your home might look something like: $[600, 1, 1, 60]$.\n",
    "However, if you live in Pittsburgh, it might look more like $[3000, 4, 3, 10]$.\n",
    "Fixed-length feature vectors like this are essential\n",
    "for most classic machine learning algorithms.\n",
    "\n",
    "What makes a problem a regression is actually\n",
    "the form of the target.\n",
    "Say that you are in the market for a new home.\n",
    "You might want to estimate the fair market value of a house,\n",
    "given some features such as above.\n",
    "The data here might consist of historical home listings\n",
    "and the labels might be the observed sales prices.\n",
    "When labels take on arbitrary numerical values\n",
    "(even within some interval),\n",
    "we call this a *regression* problem.\n",
    "The goal is to produce a model whose predictions\n",
    "closely approximate the actual label values.\n",
    "\n",
    "\n",
    "Lots of practical problems are easily described as regression problems.\n",
    "Predicting the rating that a user will assign to a movie\n",
    "can be thought of as a regression problem\n",
    "and if you designed a great algorithm\n",
    "to accomplish this feat in 2009,\n",
    "you might have won the [1-million-dollar Netflix prize](https://en.wikipedia.org/wiki/Netflix_Prize).\n",
    "Predicting the length of stay for patients in the hospital\n",
    "is also a regression problem.\n",
    "A good rule of thumb is that any *how much?* or *how many?* problem\n",
    "is likely to be regression. For example:\n",
    "\n",
    "* How many hours will this surgery take?\n",
    "* How much rainfall will this town have in the next six hours?\n",
    "\n",
    "\n",
    "Even if you have never worked with machine learning before,\n",
    "you have probably worked through a regression problem informally.\n",
    "Imagine, for example, that you had your drains repaired\n",
    "and that your contractor spent 3 hours\n",
    "removing gunk from your sewage pipes.\n",
    "Then they sent you a bill of 350 dollars.\n",
    "Now imagine that your friend hired the same contractor for 2 hours\n",
    "and received a bill of 250 dollars.\n",
    "If someone then asked you how much to expect\n",
    "on their upcoming gunk-removal invoice\n",
    "you might make some reasonable assumptions,\n",
    "such as more hours worked costs more dollars.\n",
    "You might also assume that there is some base charge\n",
    "and that the contractor then charges per hour.\n",
    "If these assumptions held true, then given these two data examples,\n",
    "you could already identify the contractor's pricing structure:\n",
    "100 dollars per hour plus 50 dollars to show up at your house.\n",
    "If you followed that much, then you already understand\n",
    "the high-level idea behind *linear* regression.\n",
    "\n",
    "In this case, we could produce the parameters\n",
    "that exactly matched the contractor's prices.\n",
    "Sometimes this is not possible,\n",
    "e.g., if some of the variation\n",
    "arises from factors beyond your two features.\n",
    "In these cases, we will try to learn models\n",
    "that minimize the distance between our predictions and the observed values.\n",
    "In most of our chapters, we will focus on\n",
    "minimizing the squared error loss function.\n",
    "As we will see later, this loss corresponds to the assumption\n",
    "that our data were corrupted by Gaussian noise.\n",
    "\n",
    "#### Classification\n",
    "\n",
    "While regression models are great\n",
    "for addressing *how many?* questions,\n",
    "lots of problems do not fit comfortably in this template.\n",
    "Consider, for example, a bank that wants\n",
    "to develop a check scanning feature for its mobile app.\n",
    "Ideally, the customer would simply snap a photo of a check\n",
    "and the app would automatically recognize the text from the image.\n",
    "Assuming that we had some ability\n",
    "to segment out image patches\n",
    "corresponding to each handwritten character,\n",
    "then the primary remaining task would be\n",
    "to determine which character among some known set\n",
    "is depicted in each image patch.\n",
    "These kinds of *which one?* problems are called *classification*\n",
    "and require a different set of tools\n",
    "from those used for regression,\n",
    "although many techniques will carry over.\n",
    "\n",
    "In *classification*, we want our model to look at features,\n",
    "e.g., the pixel values in an image,\n",
    "and then predict to which *category*\n",
    "(sometimes called a *class*)\n",
    "among some discrete set of options,\n",
    "an example belongs.\n",
    "For handwritten digits, we might have ten classes,\n",
    "corresponding to the digits 0 through 9.\n",
    "The simplest form of classification is when there are only two classes,\n",
    "a problem which we call *binary classification*.\n",
    "For example, our dataset could consist of images of animals\n",
    "and our labels  might be the classes $\\textrm{\\{cat, dog\\}}$.\n",
    "Whereas in regression we sought a regressor to output a numerical value,\n",
    "in classification we seek a classifier,\n",
    "whose output is the predicted class assignment.\n",
    "\n",
    "For reasons that we will get into as the book gets more technical,\n",
    "it can be difficult to optimize a model that can only output\n",
    "a *firm* categorical assignment,\n",
    "e.g., either \"cat\" or \"dog\".\n",
    "In these cases, it is usually much easier to express\n",
    "our model in the language of probabilities.\n",
    "Given features of an example,\n",
    "our model assigns a probability\n",
    "to each possible class.\n",
    "Returning to our animal classification example\n",
    "where the classes are $\\textrm{\\{cat, dog\\}}$,\n",
    "a classifier might see an image and output the probability\n",
    "that the image is a cat as 0.9.\n",
    "We can interpret this number by saying that the classifier\n",
    "is 90\\% sure that the image depicts a cat.\n",
    "The magnitude of the probability for the predicted class\n",
    "conveys a notion of uncertainty.\n",
    "It is not the only one available\n",
    "and we will discuss others in chapters dealing with more advanced topics.\n",
    "\n",
    "When we have more than two possible classes,\n",
    "we call the problem *multiclass classification*.\n",
    "Common examples include handwritten character recognition\n",
    "$\\textrm{\\{0, 1, 2, ... 9, a, b, c, ...\\}}$.\n",
    "While we attacked regression problems by trying\n",
    "to minimize the squared error loss function,\n",
    "the common loss function for classification problems is called *cross-entropy*,\n",
    "whose name will be demystified\n",
    "when we introduce information theory in later chapters.\n",
    "\n",
    "Note that the most likely class is not necessarily\n",
    "the one that you are going to use for your decision.\n",
    "Assume that you find a beautiful mushroom in your backyard\n",
    "as shown in :numref:`fig_death_cap`.\n",
    "\n",
    "![Death cap - do not eat!](../img/death-cap.jpg)\n",
    ":width:`200px`\n",
    ":label:`fig_death_cap`\n",
    "\n",
    "Now, assume that you built a classifier and trained it\n",
    "to predict whether a mushroom is poisonous based on a photograph.\n",
    "Say our poison-detection classifier outputs\n",
    "that the probability that\n",
    ":numref:`fig_death_cap` shows a death cap is 0.2.\n",
    "In other words, the classifier is 80\\% sure\n",
    "that our mushroom is not a death cap.\n",
    "Still, you would have to be a fool to eat it.\n",
    "That is because the certain benefit of a delicious dinner\n",
    "is not worth a 20\\% risk of dying from it.\n",
    "In other words, the effect of the uncertain risk\n",
    "outweighs the benefit by far.\n",
    "Thus, in order to make a decision about whether to eat the mushroom,\n",
    "we need to compute the expected detriment\n",
    "associated with each action\n",
    "which depends both on the likely outcomes\n",
    "and the benefits or harms associated with each.\n",
    "In this case, the detriment incurred\n",
    "by eating the mushroom\n",
    "might be $0.2 \\times \\infty + 0.8 \\times 0 = \\infty$,\n",
    "whereas the loss of discarding it\n",
    "is $0.2 \\times 0 + 0.8 \\times 1 = 0.8$.\n",
    "Our caution was justified:\n",
    "as any mycologist would tell us,\n",
    "the mushroom in :numref:`fig_death_cap`\n",
    "is actually a death cap.\n",
    "\n",
    "Classification can get much more complicated than just\n",
    "binary or multiclass classification.\n",
    "For instance, there are some variants of classification\n",
    "addressing hierarchically structured classes.\n",
    "In such cases not all errors are equal---if\n",
    "we must err, we might prefer to misclassify\n",
    "to a related class rather than a distant class.\n",
    "Usually, this is referred to as *hierarchical classification*.\n",
    "For inspiration, you might think of [Linnaeus](https://en.wikipedia.org/wiki/Carl_Linnaeus),\n",
    "who organized fauna in a hierarchy.\n",
    "\n",
    "In the case of animal classification,\n",
    "it might not be so bad to mistake\n",
    "a poodle for a schnauzer,\n",
    "but our model would pay a huge penalty\n",
    "if it confused a poodle with a dinosaur.\n",
    "Which hierarchy is relevant might depend\n",
    "on how you plan to use the model.\n",
    "For example, rattlesnakes and garter snakes\n",
    "might be close on the phylogenetic tree,\n",
    "but mistaking a rattler for a garter could have fatal consequences.\n",
    "\n",
    "#### Tagging\n",
    "\n",
    "Some classification problems fit neatly\n",
    "into the binary or multiclass classification setups.\n",
    "For example, we could train a normal binary classifier\n",
    "to distinguish cats from dogs.\n",
    "Given the current state of computer vision,\n",
    "we can do this easily, with off-the-shelf tools.\n",
    "Nonetheless, no matter how accurate our model gets,\n",
    "we might find ourselves in trouble when the classifier\n",
    "encounters an image of the *Town Musicians of Bremen*,\n",
    "a popular German fairy tale featuring four animals\n",
    "(:numref:`fig_stackedanimals`).\n",
    "\n",
    "![A donkey, a dog, a cat, and a rooster.](../img/stackedanimals.png)\n",
    ":width:`300px`\n",
    ":label:`fig_stackedanimals`\n",
    "\n",
    "As you can see, the photo features a cat,\n",
    "a rooster, a dog, and a donkey,\n",
    "with some trees in the background.\n",
    "If we anticipate encountering such images,\n",
    "multiclass classification might not be\n",
    "the right problem formulation.\n",
    "Instead, we might want to give the model the option of\n",
    "saying the image depicts a cat, a dog, a donkey,\n",
    "*and* a rooster.\n",
    "\n",
    "The problem of learning to predict classes that are\n",
    "not mutually exclusive is called *multi-label classification*.\n",
    "Auto-tagging problems are typically best described\n",
    "in terms of multi-label classification.\n",
    "Think of the tags people might apply\n",
    "to posts on a technical blog,\n",
    "e.g., \"machine learning\", \"technology\", \"gadgets\",\n",
    "\"programming languages\", \"Linux\", \"cloud computing\", \"AWS\".\n",
    "A typical article might have 5--10 tags applied.\n",
    "Typically, tags will exhibit some correlation structure.\n",
    "Posts about \"cloud computing\" are likely to mention \"AWS\"\n",
    "and posts about \"machine learning\" are likely to mention \"GPUs\".\n",
    "\n",
    "Sometimes such tagging problems\n",
    "draw on enormous label sets.\n",
    "The National Library of Medicine\n",
    "employs many professional annotators\n",
    "who associate each article to be indexed in PubMed\n",
    "with a set of tags drawn from the\n",
    "Medical Subject Headings (MeSH) ontology,\n",
    "a collection of roughly 28,000 tags.\n",
    "Correctly tagging articles is important\n",
    "because it allows researchers to conduct\n",
    "exhaustive reviews of the literature.\n",
    "This is a time-consuming process and typically there is a one-year lag between archiving and tagging.\n",
    "Machine learning can provide provisional tags\n",
    "until each article has a proper manual review.\n",
    "Indeed, for several years, the BioASQ organization\n",
    "has [hosted competitions](http://bioasq.org/)\n",
    "for this task.\n",
    "\n",
    "#### Search\n",
    "\n",
    "In the field of information retrieval,\n",
    "we often impose ranks on sets of items.\n",
    "Take web search for example.\n",
    "The goal is less to determine *whether*\n",
    "a particular page is relevant for a query, \n",
    "but rather which, among a set of relevant results,\n",
    "should be shown most prominently\n",
    "to a particular user.\n",
    "One way of doing this might be\n",
    "to first assign a score\n",
    "to every element in the set\n",
    "and then to retrieve the top-rated elements.\n",
    "[PageRank](https://en.wikipedia.org/wiki/PageRank),\n",
    "the original secret sauce behind the Google search engine,\n",
    "was an early example of such a scoring system.\n",
    "Weirdly, the scoring provided by PageRank\n",
    "did not depend on the actual query.\n",
    "Instead, they relied on a simple relevance filter\n",
    "to identify the set of relevant candidates\n",
    "and then used PageRank to prioritize\n",
    "the more authoritative pages.\n",
    "Nowadays, search engines use machine learning and behavioral models\n",
    "to obtain query-dependent relevance scores.\n",
    "There are entire academic conferences devoted to this subject.\n",
    "\n",
    "#### Recommender Systems\n",
    ":label:`subsec_recommender_systems`\n",
    "\n",
    "Recommender systems are another problem setting\n",
    "that is related to search and ranking.\n",
    "The problems are similar insofar as the goal\n",
    "is to display a set of items relevant to the user.\n",
    "The main difference is the emphasis on *personalization*\n",
    "to specific users in the context of recommender systems.\n",
    "For instance, for movie recommendations,\n",
    "the results page for a science fiction fan\n",
    "and the results page\n",
    "for a connoisseur of Peter Sellers comedies\n",
    "might differ significantly.\n",
    "Similar problems pop up in other recommendation settings,\n",
    "e.g., for retail products, music, and news recommendation.\n",
    "\n",
    "In some cases, customers provide explicit feedback,\n",
    "communicating how much they liked a particular product\n",
    "(e.g., the product ratings and reviews\n",
    "on Amazon, IMDb, or Goodreads).\n",
    "In other cases, they provide implicit feedback,\n",
    "e.g., by skipping titles on a playlist,\n",
    "which might indicate \n",
    "dissatisfaction or maybe just\n",
    "indicate\n",
    "that the song was inappropriate in context.\n",
    "In the simplest formulations,\n",
    "these systems are trained\n",
    "to estimate some score,\n",
    "such as an expected star rating\n",
    "or the probability that a given user\n",
    "will purchase a particular item.\n",
    "\n",
    "Given such a model, for any given user,\n",
    "we could retrieve the set of objects with the largest scores,\n",
    "which could then be recommended to the user.\n",
    "Production systems are considerably more advanced\n",
    "and take detailed user activity and item characteristics\n",
    "into account when computing such scores.\n",
    ":numref:`fig_deeplearning_amazon` displays the deep learning books\n",
    "recommended by Amazon based on personalization algorithms\n",
    "tuned to capture Aston's preferences.\n",
    "\n",
    "![Deep learning books recommended by Amazon.](../img/deeplearning-amazon.jpg)\n",
    ":label:`fig_deeplearning_amazon`\n",
    "\n",
    "Despite their tremendous economic value,\n",
    "recommender systems\n",
    "naively built on top of predictive models\n",
    "suffer some serious conceptual flaws.\n",
    "To start, we only observe *censored feedback*:\n",
    "users preferentially rate movies\n",
    "that they feel strongly about.\n",
    "For example, on a five-point scale,\n",
    "you might notice that items receive\n",
    "many one- and five-star ratings\n",
    "but that there are conspicuously few three-star ratings.\n",
    "Moreover, current purchase habits are often a result\n",
    "of the recommendation algorithm currently in place,\n",
    "but learning algorithms do not always take this detail into account.\n",
    "Thus it is possible for feedback loops to form\n",
    "where a recommender system preferentially pushes an item\n",
    "that is then taken to be better (due to greater purchases)\n",
    "and in turn is recommended even more frequently.\n",
    "Many of these problems---about\n",
    "how to deal with censoring,\n",
    "incentives, and feedback loops---are important open research questions.\n",
    "\n",
    "#### Sequence Learning\n",
    "\n",
    "So far, we have looked at problems where we have\n",
    "some fixed number of inputs and produce a fixed number of outputs.\n",
    "For example, we considered predicting house prices\n",
    "given a fixed set of features:\n",
    "square footage, number of bedrooms,\n",
    "number of bathrooms, and the transit time to downtown.\n",
    "We also discussed mapping from an image (of fixed dimension)\n",
    "to the predicted probabilities that it belongs\n",
    "to each among a fixed number of classes\n",
    "and predicting star ratings associated with purchases\n",
    "based on the user ID and product ID alone.\n",
    "In these cases, once our model is trained,\n",
    "after each test example is fed into our model,\n",
    "it is immediately forgotten.\n",
    "We assumed that successive observations were independent\n",
    "and thus there was no need to hold on to this context.\n",
    "\n",
    "But how should we deal with video snippets?\n",
    "In this case, each snippet might consist of a different number of frames.\n",
    "And our guess of what is going on in each frame might be much stronger\n",
    "if we take into account the previous or succeeding frames.\n",
    "The same goes for language.\n",
    "For example, one popular deep learning problem is machine translation:\n",
    "the task of ingesting sentences in some source language\n",
    "and predicting their translations in another language.\n",
    "\n",
    "Such problems also occur in medicine.\n",
    "We might want a model to monitor patients in the intensive care unit\n",
    "and to fire off alerts whenever their risk of dying in the next 24 hours\n",
    "exceeds some threshold.\n",
    "Here, we would not throw away everything\n",
    "that we know about the patient history every hour,\n",
    "because we might not want to make predictions based only\n",
    "on the most recent measurements.\n",
    "\n",
    "Questions like these are among the most\n",
    "exciting applications of machine learning\n",
    "and they are instances of *sequence learning*.\n",
    "They require a model either to ingest sequences of inputs\n",
    "or to emit sequences of outputs (or both).\n",
    "Specifically, *sequence-to-sequence learning* considers problems\n",
    "where both inputs and outputs consist of variable-length sequences.\n",
    "Examples include machine translation\n",
    "and speech-to-text transcription.\n",
    "While it is impossible to consider\n",
    "all types of sequence transformations,\n",
    "the following special cases are worth mentioning.\n",
    "\n",
    "**Tagging and Parsing**.\n",
    "This involves annotating a text sequence with attributes.\n",
    "Here, the inputs and outputs are *aligned*,\n",
    "i.e., they are of the same number\n",
    "and occur in a corresponding order.\n",
    "For instance, in *part-of-speech (PoS) tagging*,\n",
    "we annotate every word in a sentence\n",
    "with the corresponding part of speech,\n",
    "i.e., \"noun\" or \"direct object\".\n",
    "Alternatively, we might want to know\n",
    "which groups of contiguous words refer to named entities,\n",
    "like *people*, *places*, or *organizations*.\n",
    "In the cartoonishly simple example below,\n",
    "we might just want to indicate whether or not any word in the sentence is part of a named entity (tagged as \"Ent\").\n",
    "\n",
    "```text\n",
    "Tom has dinner in Washington with Sally\n",
    "Ent  -    -    -     Ent      -    Ent\n",
    "```\n",
    "\n",
    "**Automatic Speech Recognition**.\n",
    "With speech recognition, the input sequence\n",
    "is an audio recording of a speaker (:numref:`fig_speech`),\n",
    "and the output is a transcript of what the speaker said.\n",
    "The challenge is that there are many more audio frames\n",
    "(sound is typically sampled at 8kHz or 16kHz)\n",
    "than text, i.e., there is no 1:1 correspondence between audio and text,\n",
    "since thousands of samples may\n",
    "correspond to a single spoken word.\n",
    "These are sequence-to-sequence learning problems,\n",
    "where the output is much shorter than the input.\n",
    "While humans are remarkably good at recognizing speech,\n",
    "even from low-quality audio,\n",
    "getting computers to perform the same feat\n",
    "is a formidable challenge.\n",
    "\n",
    "![`-D-e-e-p- L-ea-r-ni-ng-` in an audio recording.](../img/speech.png)\n",
    ":width:`700px`\n",
    ":label:`fig_speech`\n",
    "\n",
    "**Text to Speech**.\n",
    "This is the inverse of automatic speech recognition.\n",
    "Here, the input is text and the output is an audio file.\n",
    "In this case, the output is much longer than the input.\n",
    "\n",
    "**Machine Translation**.\n",
    "Unlike the case of speech recognition,\n",
    "where corresponding inputs and outputs\n",
    "occur in the same order,\n",
    "in machine translation,\n",
    "unaligned data poses a new challenge.\n",
    "Here the input and output sequences\n",
    "can have different lengths,\n",
    "and the corresponding regions\n",
    "of the respective sequences\n",
    "may appear in a different order.\n",
    "Consider the following illustrative example\n",
    "of the peculiar tendency of Germans\n",
    "to place the verbs at the end of sentences:\n",
    "\n",
    "```text\n",
    "German:           Haben Sie sich schon dieses grossartige Lehrwerk angeschaut?\n",
    "English:          Have you already looked at this excellent textbook?\n",
    "Wrong alignment:  Have you yourself already this excellent textbook looked at?\n",
    "```\n",
    "\n",
    "Many related problems pop up in other learning tasks.\n",
    "For instance, determining the order in which a user\n",
    "reads a webpage is a two-dimensional layout analysis problem.\n",
    "Dialogue problems exhibit all kinds of additional complications,\n",
    "where determining what to say next requires taking into account\n",
    "real-world knowledge and the prior state of the conversation\n",
    "across long temporal distances.\n",
    "Such topics are active areas of research.\n",
    "\n",
    "### Unsupervised and Self-Supervised Learning\n",
    "\n",
    "The previous examples focused on supervised learning,\n",
    "where we feed the model a giant dataset\n",
    "containing both the features and corresponding label values.\n",
    "You could think of the supervised learner as having\n",
    "an extremely specialized job and an extremely dictatorial boss.\n",
    "The boss stands over the learner's shoulder and tells them exactly what to do\n",
    "in every situation until they learn to map from situations to actions.\n",
    "Working for such a boss sounds pretty lame.\n",
    "On the other hand, pleasing such a boss is pretty easy.\n",
    "You just recognize the pattern as quickly as possible\n",
    "and imitate the boss's actions.\n",
    "\n",
    "Considering the opposite situation,\n",
    "it could be frustrating to work for a boss\n",
    "who has no idea what they want you to do.\n",
    "However, if you plan to be a data scientist,\n",
    "you had better get used to it.\n",
    "The boss might just hand you a giant dump of data\n",
    "and tell you to *do some data science with it!*\n",
    "This sounds vague because it is vague.\n",
    "We call this class of problems *unsupervised learning*,\n",
    "and the type and number of questions we can ask\n",
    "is limited only by our creativity.\n",
    "We will address unsupervised learning techniques\n",
    "in later chapters.\n",
    "To whet your appetite for now,\n",
    "we describe a few of the following questions you might ask.\n",
    "\n",
    "* Can we find a small number of prototypes\n",
    "that accurately summarize the data?\n",
    "Given a set of photos, can we group them into landscape photos,\n",
    "pictures of dogs, babies, cats, and mountain peaks?\n",
    "Likewise, given a collection of users' browsing activities,\n",
    "can we group them into users with similar behavior?\n",
    "This problem is typically known as *clustering*.\n",
    "* Can we find a small number of parameters\n",
    "that accurately capture the relevant properties of the data?\n",
    "The trajectories of a ball are well described\n",
    "by velocity, diameter, and mass of the ball.\n",
    "Tailors have developed a small number of parameters\n",
    "that describe human body shape fairly accurately\n",
    "for the purpose of fitting clothes.\n",
    "These problems are referred to as *subspace estimation*.\n",
    "If the dependence is linear, it is called *principal component analysis*.\n",
    "* Is there a representation of (arbitrarily structured) objects\n",
    "in Euclidean space\n",
    "such that symbolic properties can be well matched?\n",
    "This can be used to describe entities and their relations,\n",
    "such as \"Rome\" $-$ \"Italy\" $+$ \"France\" $=$ \"Paris\".\n",
    "* Is there a description of the root causes\n",
    "of much of the data that we observe?\n",
    "For instance, if we have demographic data\n",
    "about house prices, pollution, crime, location,\n",
    "education, and salaries, can we discover\n",
    "how they are related simply based on empirical data?\n",
    "The fields concerned with *causality* and\n",
    "*probabilistic graphical models* tackle such questions.\n",
    "* Another important and exciting recent development in unsupervised learning\n",
    "is the advent of *deep generative models*.\n",
    "These models estimate the density of the data,\n",
    "either explicitly or *implicitly*.\n",
    "Once trained, we can use a generative model\n",
    "either to score examples according to how likely they are,\n",
    "or to sample synthetic examples from the learned distribution.\n",
    "Early deep learning breakthroughs in generative modeling\n",
    "came with the invention of *variational autoencoders* :cite:`Kingma.Welling.2014,rezende2014stochastic`\n",
    "and continued with the development of *generative adversarial networks* :cite:`Goodfellow.Pouget-Abadie.Mirza.ea.2014`.\n",
    "More recent advances include normalizing flows :cite:`dinh2014nice,dinh2017density` and\n",
    "diffusion models :cite:`sohl2015deep,song2019generative,ho2020denoising,song2021score`.\n",
    "\n",
    "\n",
    "\n",
    "A further development in unsupervised learning\n",
    "has been the rise of *self-supervised learning*,\n",
    "techniques that leverage some aspect of the unlabeled data\n",
    "to provide supervision.\n",
    "For text, we can train models\n",
    "to \"fill in the blanks\"\n",
    "by predicting randomly masked words\n",
    "using their surrounding words (contexts)\n",
    "in big corpora without any labeling effort :cite:`Devlin.Chang.Lee.ea.2018`!\n",
    "For images, we may train models\n",
    "to tell the relative position\n",
    "between two cropped regions\n",
    "of the same image :cite:`Doersch.Gupta.Efros.2015`,\n",
    "to predict an occluded part of an image\n",
    "based on the remaining portions of the image,\n",
    "or to predict whether two examples\n",
    "are perturbed versions of the same underlying image.\n",
    "Self-supervised models often learn representations\n",
    "that are subsequently leveraged\n",
    "by fine-tuning the resulting models\n",
    "on some downstream task of interest.\n",
    "\n",
    "\n",
    "### Interacting with an Environment\n",
    "\n",
    "So far, we have not discussed where data actually comes from,\n",
    "or what actually happens when a machine learning model generates an output.\n",
    "That is because supervised learning and unsupervised learning\n",
    "do not address these issues in a very sophisticated way.\n",
    "In each case, we grab a big pile of data upfront,\n",
    "then set our pattern recognition machines in motion\n",
    "without ever interacting with the environment again.\n",
    "Because all the learning takes place\n",
    "after the algorithm is disconnected from the environment,\n",
    "this is sometimes called *offline learning*.\n",
    "For example, supervised learning assumes\n",
    "the simple interaction pattern\n",
    "depicted in :numref:`fig_data_collection`.\n",
    "\n",
    "![Collecting data for supervised learning from an environment.](../img/data-collection.svg)\n",
    ":label:`fig_data_collection`\n",
    "\n",
    "This simplicity of offline learning has its charms.\n",
    "The upside is that we can worry\n",
    "about pattern recognition in isolation,\n",
    "with no concern about complications arising\n",
    "from interactions with a dynamic environment.\n",
    "But this problem formulation is limiting.\n",
    "If you grew up reading Asimov's Robot novels,\n",
    "then you probably picture artificially intelligent agents\n",
    "capable not only of making predictions,\n",
    "but also of taking actions in the world.\n",
    "We want to think about intelligent *agents*,\n",
    "not just predictive models.\n",
    "This means that we need to think about choosing *actions*,\n",
    "not just making predictions.\n",
    "In contrast to mere predictions,\n",
    "actions actually impact the environment.\n",
    "If we want to train an intelligent agent,\n",
    "we must account for the way its actions might\n",
    "impact the future observations of the agent, and so offline learning is inappropriate.\n",
    "\n",
    "Considering the interaction with an environment\n",
    "opens a whole set of new modeling questions.\n",
    "The following are just a few examples.\n",
    "\n",
    "* Does the environment remember what we did previously?\n",
    "* Does the environment want to help us, e.g., a user reading text into a speech recognizer?\n",
    "* Does the environment want to beat us, e.g., spammers adapting their emails to evade spam filters?\n",
    "* Does the environment have shifting dynamics? For example, would future data always resemble the past or would the patterns change over time, either naturally or in response to our automated tools?\n",
    "\n",
    "These questions raise the problem of *distribution shift*,\n",
    "where training and test data are different.\n",
    "An example of this, that many of us may have met, is when taking exams written by a lecturer,\n",
    "while the homework was composed by their teaching assistants.\n",
    "Next, we briefly describe reinforcement learning,\n",
    "a rich framework for posing learning problems in which\n",
    "an agent interacts with an environment.\n",
    "\n",
    "\n",
    "### Reinforcement Learning\n",
    "\n",
    "If you are interested in using machine learning\n",
    "to develop an agent that interacts with an environment\n",
    "and takes actions, then you are probably going to wind up\n",
    "focusing on *reinforcement learning*.\n",
    "This might include applications to robotics,\n",
    "to dialogue systems,\n",
    "and even to developing artificial intelligence (AI)\n",
    "for video games.\n",
    "*Deep reinforcement learning*, which applies\n",
    "deep learning to reinforcement learning problems,\n",
    "has surged in popularity.\n",
    "The breakthrough deep Q-network, that beat humans\n",
    "at Atari games using only the visual input :cite:`mnih2015human`,\n",
    "and the AlphaGo program, which dethroned the world champion\n",
    "at the board game Go :cite:`Silver.Huang.Maddison.ea.2016`,\n",
    "are two prominent examples.\n",
    "\n",
    "Reinforcement learning gives a very general statement of a problem\n",
    "in which an agent interacts with an environment over a series of time steps.\n",
    "At each time step, the agent receives some *observation*\n",
    "from the environment and must choose an *action*\n",
    "that is subsequently transmitted back to the environment\n",
    "via some mechanism (sometimes called an *actuator*), when, after each loop, \n",
    "the agent receives a reward from the environment.\n",
    "This process is illustrated in :numref:`fig_rl-environment`.\n",
    "The agent then receives a subsequent observation,\n",
    "and chooses a subsequent action, and so on.\n",
    "The behavior of a reinforcement learning agent is governed by a *policy*.\n",
    "In brief, a *policy* is just a function that maps\n",
    "from observations of the environment to actions.\n",
    "The goal of reinforcement learning is to produce good policies.\n",
    "\n",
    "![The interaction between reinforcement learning and an environment.](../img/rl-environment.svg)\n",
    ":label:`fig_rl-environment`\n",
    "\n",
    "It is hard to overstate the generality\n",
    "of the reinforcement learning framework.\n",
    "For example, supervised learning\n",
    "can be recast as reinforcement learning.\n",
    "Say we had a classification problem.\n",
    "We could create a reinforcement learning agent\n",
    "with one action corresponding to each class.\n",
    "We could then create an environment which gave a reward\n",
    "that was exactly equal to the loss function\n",
    "from the original supervised learning problem.\n",
    "\n",
    "Further, reinforcement learning\n",
    "can also address many problems\n",
    "that supervised learning cannot.\n",
    "For example, in supervised learning,\n",
    "we always expect that the training input\n",
    "comes associated with the correct label.\n",
    "But in reinforcement learning,\n",
    "we do not assume that, for each observation\n",
    "the environment tells us the optimal action.\n",
    "In general, we just get some reward.\n",
    "Moreover, the environment may not even tell us\n",
    "which actions led to the reward.\n",
    "\n",
    "Consider the game of chess.\n",
    "The only real reward signal comes at the end of the game\n",
    "when we either win, earning a reward of, say, $1$,\n",
    "or when we lose, receiving a reward of, say, $-1$.\n",
    "So reinforcement learners must deal\n",
    "with the *credit assignment* problem:\n",
    "determining which actions to credit or blame for an outcome.\n",
    "The same goes for an employee\n",
    "who gets a promotion on October 11.\n",
    "That promotion likely reflects a number\n",
    "of well-chosen actions over the previous year.\n",
    "Getting promoted in the future requires figuring out\n",
    "which actions along the way led to the earlier promotions.\n",
    "\n",
    "Reinforcement learners may also have to deal\n",
    "with the problem of partial observability.\n",
    "That is, the current observation might not\n",
    "tell you everything about your current state.\n",
    "Say your cleaning robot found itself trapped\n",
    "in one of many identical closets in your house.\n",
    "Rescuing the robot involves inferring\n",
    "its precise location which might require considering earlier observations prior to it entering the closet.\n",
    "\n",
    "Finally, at any given point, reinforcement learners\n",
    "might know of one good policy,\n",
    "but there might be many other better policies\n",
    "that the agent has never tried.\n",
    "The reinforcement learner must constantly choose\n",
    "whether to *exploit* the best (currently) known strategy as a policy,\n",
    "or to *explore* the space of strategies,\n",
    "potentially giving up some short-term reward\n",
    "in exchange for knowledge.\n",
    "\n",
    "The general reinforcement learning problem\n",
    "has a very general setting.\n",
    "Actions affect subsequent observations.\n",
    "Rewards are only observed when they correspond to the chosen actions.\n",
    "The environment may be either fully or partially observed.\n",
    "Accounting for all this complexity at once may be asking too much.\n",
    "Moreover, not every practical problem exhibits all this complexity.\n",
    "As a result, researchers have studied a number of\n",
    "special cases of reinforcement learning problems.\n",
    "\n",
    "When the environment is fully observed,\n",
    "we call the reinforcement learning problem a *Markov decision process*.\n",
    "When the state does not depend on the previous actions,\n",
    "we call it a *contextual bandit problem*.\n",
    "When there is no state, just a set of available actions\n",
    "with initially unknown rewards, we have the classic *multi-armed bandit problem*.\n",
    "\n",
    "## Roots\n",
    "\n",
    "We have just reviewed a small subset of problems\n",
    "that machine learning can address.\n",
    "For a diverse set of machine learning problems,\n",
    "deep learning provides powerful tools for their solution.\n",
    "Although many deep learning methods are recent inventions,\n",
    "the core ideas behind learning from data\n",
    "have been studied for centuries.\n",
    "In fact, humans have held the desire to analyze data\n",
    "and to predict future outcomes for \n",
    "ages, and it is this desire that is at the root of much of natural science and mathematics.\n",
    "Two examples are the Bernoulli distribution, named after\n",
    "[Jacob Bernoulli (1655--1705)](https://en.wikipedia.org/wiki/Jacob_Bernoulli),\n",
    "and the Gaussian distribution discovered\n",
    "by [Carl Friedrich Gauss (1777--1855)](https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss).\n",
    "Gauss invented, for instance, the least mean squares algorithm,\n",
    "which is still used today for a multitude of problems\n",
    "from insurance calculations to medical diagnostics.\n",
    "Such tools enhanced the experimental approach\n",
    "in the natural sciences---for instance, Ohm's law\n",
    "relating current and voltage in a resistor\n",
    "is perfectly described by a linear model.\n",
    "\n",
    "Even in the middle ages, mathematicians\n",
    "had a keen intuition of estimates.\n",
    "For instance, the geometry book of [Jacob Köbel (1460--1533)](https://www.maa.org/press/periodicals/convergence/mathematical-treasures-jacob-kobels-geometry)\n",
    "illustrates averaging the length of 16 adult men's feet\n",
    "to estimate the typical foot length in the population (:numref:`fig_koebel`).\n",
    "\n",
    "![Estimating the length of a foot.](../img/koebel.jpg)\n",
    ":width:`500px`\n",
    ":label:`fig_koebel`\n",
    "\n",
    "\n",
    "As a group of individuals exited a church,\n",
    "16 adult men were asked to line up in a row\n",
    "and have their feet measured.\n",
    "The sum of these measurements was then divided by 16\n",
    "to obtain an estimate for what now is called one foot.\n",
    "This \"algorithm\" was later improved\n",
    "to deal with misshapen feet;\n",
    "The two men with the shortest and longest feet were sent away,\n",
    "averaging only over the remainder.\n",
    "This is among the earliest examples\n",
    "of a trimmed mean estimate.\n",
    "\n",
    "Statistics really took off with the availability and collection of data.\n",
    "One of its pioneers, [Ronald Fisher (1890--1962)](https://en.wikipedia.org/wiki/Ronald_Fisher),\n",
    "contributed significantly to its theory\n",
    "and also its applications in genetics.\n",
    "Many of his algorithms (such as linear discriminant analysis)\n",
    "and concepts (such as the Fisher information matrix)\n",
    "still hold a prominent place\n",
    "in the foundations of modern statistics.\n",
    "Even his data resources had a lasting impact.\n",
    "The Iris dataset that Fisher released in 1936\n",
    "is still sometimes used to demonstrate\n",
    "machine learning algorithms.\n",
    "Fisher was also a proponent of eugenics,\n",
    "which should remind us that the morally dubious use of data science\n",
    "has as long and enduring a history as its productive use\n",
    "in industry and the natural sciences.\n",
    "\n",
    "\n",
    "Other influences for machine learning\n",
    "came from the information theory of\n",
    "[Claude Shannon (1916--2001)](https://en.wikipedia.org/wiki/Claude_Shannon)\n",
    "and the theory of computation proposed by\n",
    "[Alan Turing (1912--1954)](https://en.wikipedia.org/wiki/Alan_Turing).\n",
    "Turing posed the question \"can machines think?”\n",
    "in his famous paper *Computing Machinery and Intelligence* :cite:`Turing.1950`.\n",
    "Describing what is now known as the Turing test, he proposed that a machine\n",
    "can be considered *intelligent* if it is difficult\n",
    "for a human evaluator to distinguish between the replies\n",
    "from a machine and those of a human, based purely on textual interactions.\n",
    "\n",
    "Further influences came from neuroscience and psychology.\n",
    "After all, humans clearly exhibit intelligent behavior.\n",
    "Many scholars have asked whether one could explain\n",
    "and possibly reverse engineer this capacity.\n",
    "One of the first biologically inspired algorithms\n",
    "was formulated by [Donald Hebb (1904--1985)](https://en.wikipedia.org/wiki/Donald_O._Hebb).\n",
    "In his groundbreaking book *The Organization of Behavior* :cite:`Hebb.1949`,\n",
    "he posited that neurons learn by positive reinforcement.\n",
    "This became known as the Hebbian learning rule.\n",
    "These ideas inspired later work, such as\n",
    "Rosenblatt's perceptron learning algorithm,\n",
    "and laid the foundations of many stochastic gradient descent algorithms\n",
    "that underpin deep learning today:\n",
    "reinforce desirable behavior and diminish undesirable behavior\n",
    "to obtain good settings of the parameters in a neural network.\n",
    "\n",
    "Biological inspiration is what gave *neural networks* their name.\n",
    "For over a century (dating back to the models of Alexander Bain, 1873,\n",
    "and James Sherrington, 1890), researchers have tried to assemble\n",
    "computational circuits that resemble networks of interacting neurons.\n",
    "Over time, the interpretation of biology has become less literal,\n",
    "but the name stuck. At its heart lie a few key principles\n",
    "that can be found in most networks today:\n",
    "\n",
    "* The alternation of linear and nonlinear processing units, often referred to as *layers*.\n",
    "* The use of the chain rule (also known as *backpropagation*) for adjusting parameters in the entire network at once.\n",
    "\n",
    "After initial rapid progress, research in neural networks\n",
    "languished from around 1995 until 2005.\n",
    "This was mainly due to two reasons.\n",
    "First, training a network is computationally very expensive.\n",
    "While random-access memory was plentiful at the end of the past century,\n",
    "computational power was scarce.\n",
    "Second, datasets were relatively small.\n",
    "In fact, Fisher's Iris dataset from 1936\n",
    "was still a popular tool for testing the efficacy of algorithms.\n",
    "The MNIST dataset with its 60,000 handwritten digits was considered huge.\n",
    "\n",
    "Given the scarcity of data and computation,\n",
    "strong statistical tools such as kernel methods,\n",
    "decision trees, and graphical models\n",
    "proved empirically superior in many applications.\n",
    "Moreover, unlike neural networks,\n",
    "they did not require weeks to train\n",
    "and provided predictable results\n",
    "with strong theoretical guarantees.\n",
    "\n",
    "\n",
    "## The Road to Deep Learning\n",
    "\n",
    "Much of this changed with the availability\n",
    "of massive amounts of data,\n",
    "thanks to the World Wide Web,\n",
    "the advent of companies serving\n",
    "hundreds of millions of users online,\n",
    "a dissemination of low-cost, high-quality sensors,\n",
    "inexpensive data storage (Kryder's law),\n",
    "and cheap computation (Moore's law).\n",
    "In particular, the landscape of computation in deep learning\n",
    "was revolutionized by advances in GPUs that were originally engineered for computer gaming.\n",
    "Suddenly algorithms and models\n",
    "that seemed computationally infeasible\n",
    "were within reach.\n",
    "This is best illustrated in :numref:`tab_intro_decade`.\n",
    "\n",
    ":Dataset vs. computer memory and computational power\n",
    ":label:`tab_intro_decade`\n",
    "\n",
    "|Decade|Dataset|Memory|Floating point calculations per second|\n",
    "|:--|:-|:-|:-|\n",
    "|1970|100 (Iris)|1 KB|100 KF (Intel 8080)|\n",
    "|1980|1 K (house prices in Boston)|100 KB|1 MF (Intel 80186)|\n",
    "|1990|10 K (optical character recognition)|10 MB|10 MF (Intel 80486)|\n",
    "|2000|10 M (web pages)|100 MB|1 GF (Intel Core)|\n",
    "|2010|10 G (advertising)|1 GB|1 TF (NVIDIA C2050)|\n",
    "|2020|1 T (social network)|100 GB|1 PF (NVIDIA DGX-2)|\n",
    "\n",
    "\n",
    "Note that random-access memory has not kept pace with the growth in data.\n",
    "At the same time, increases in computational power\n",
    "have outpaced the growth in datasets.\n",
    "This means that statistical models\n",
    "need to become more memory efficient,\n",
    "and so they are free to spend more computer cycles\n",
    "optimizing parameters, thanks to\n",
    "the increased compute budget.\n",
    "Consequently, the sweet spot in machine learning and statistics\n",
    "moved from (generalized) linear models and kernel methods\n",
    "to deep neural networks.\n",
    "This is also one of the reasons why many of the mainstays\n",
    "of deep learning, such as multilayer perceptrons\n",
    ":cite:`McCulloch.Pitts.1943`, convolutional neural networks\n",
    ":cite:`LeCun.Bottou.Bengio.ea.1998`, long short-term memory\n",
    ":cite:`Hochreiter.Schmidhuber.1997`,\n",
    "and Q-Learning :cite:`Watkins.Dayan.1992`,\n",
    "were essentially \"rediscovered\" in the past decade,\n",
    "after lying comparatively dormant for considerable time.\n",
    "\n",
    "The recent progress in statistical models, applications, and algorithms\n",
    "has sometimes been likened to the Cambrian explosion:\n",
    "a moment of rapid progress in the evolution of species.\n",
    "Indeed, the state of the art is not just a mere consequence\n",
    "of available resources applied to decades-old algorithms.\n",
    "Note that the list of ideas below barely scratches the surface\n",
    "of what has helped researchers achieve tremendous progress\n",
    "over the past decade.\n",
    "\n",
    "\n",
    "* Novel methods for capacity control, such as *dropout*\n",
    "  :cite:`Srivastava.Hinton.Krizhevsky.ea.2014`,\n",
    "  have helped to mitigate overfitting.\n",
    "  Here, noise is injected :cite:`Bishop.1995`\n",
    "  throughout the neural network during training.\n",
    "* *Attention mechanisms* solved a second problem\n",
    "  that had plagued statistics for over a century:\n",
    "  how to increase the memory and complexity of a system without\n",
    "  increasing the number of learnable parameters.\n",
    "  Researchers found an elegant solution\n",
    "  by using what can only be viewed as\n",
    "  a *learnable pointer structure* :cite:`Bahdanau.Cho.Bengio.2014`.\n",
    "  Rather than having to remember an entire text sequence, e.g.,\n",
    "  for machine translation in a fixed-dimensional representation,\n",
    "  all that needed to be stored was a pointer to the intermediate state\n",
    "  of the translation process. This allowed for significantly\n",
    "  increased accuracy for long sequences, since the model\n",
    "  no longer needed to remember the entire sequence before\n",
    "  commencing the generation of a new one.\n",
    "* Built solely on attention mechanisms,\n",
    "  the *Transformer* architecture :cite:`Vaswani.Shazeer.Parmar.ea.2017` has demonstrated superior *scaling* behavior: it performs better with an increase in dataset size, model size, and amount of training compute :cite:`kaplan2020scaling`. This architecture has demonstrated compelling success in a wide range of areas,\n",
    "  such as natural language processing :cite:`Devlin.Chang.Lee.ea.2018,brown2020language`, computer vision :cite:`Dosovitskiy.Beyer.Kolesnikov.ea.2021,liu2021swin`, speech recognition :cite:`gulati2020conformer`, reinforcement learning :cite:`chen2021decision`, and graph neural networks :cite:`dwivedi2020generalization`. For example, a single Transformer pretrained on modalities\n",
    "  as diverse as text, images, joint torques, and button presses\n",
    "  can play Atari, caption images, chat,\n",
    "  and control a robot :cite:`reed2022generalist`.\n",
    "* Modeling probabilities of text sequences, *language models* can predict text given other text. Scaling up the data, model, and compute has unlocked a growing number of capabilities of language models to perform desired tasks via human-like text generation based on input text :cite:`brown2020language,rae2021scaling,hoffmann2022training,chowdhery2022palm,openai2023gpt4,anil2023palm,touvron2023llama,touvron2023llama2`. For instance, aligning language models with human intent :cite:`ouyang2022training`, OpenAI's [ChatGPT](https://chat.openai.com/) allows users to interact with it in a conversational way to solve problems, such as code debugging and creative writing.\n",
    "* Multi-stage designs, e.g., via the memory networks\n",
    "  :cite:`Sukhbaatar.Weston.Fergus.ea.2015`\n",
    "  and the neural programmer-interpreter :cite:`Reed.De-Freitas.2015`\n",
    "  permitted statistical modelers to describe iterative approaches to reasoning.\n",
    "  These tools allow for an internal state of the deep neural network\n",
    "  to be modified repeatedly,\n",
    "  thus carrying out subsequent steps\n",
    "  in a chain of reasoning, just as a processor\n",
    "  can modify memory for a computation.\n",
    "* A key development in *deep generative modeling* was the invention\n",
    "  of *generative adversarial networks*\n",
    "  :cite:`Goodfellow.Pouget-Abadie.Mirza.ea.2014`.\n",
    "  Traditionally, statistical methods for density estimation\n",
    "  and generative models focused on finding proper probability distributions\n",
    "  and (often approximate) algorithms for sampling from them.\n",
    "  As a result, these algorithms were largely limited by the lack of\n",
    "  flexibility inherent in the statistical models.\n",
    "  The crucial innovation in generative adversarial networks was to replace the sampler\n",
    "  by an arbitrary algorithm with differentiable parameters.\n",
    "  These are then adjusted in such a way that the discriminator\n",
    "  (effectively a two-sample test) cannot distinguish fake from real data.\n",
    "  Through the ability to use arbitrary algorithms to generate data,\n",
    "  density estimation was opened up to a wide variety of techniques.\n",
    "  Examples of galloping zebras :cite:`Zhu.Park.Isola.ea.2017`\n",
    "  and of fake celebrity faces :cite:`Karras.Aila.Laine.ea.2017`\n",
    "  are each testimony to this progress.\n",
    "  Even amateur doodlers can produce\n",
    "  photorealistic images just based on sketches describing the layout of a scene :cite:`Park.Liu.Wang.ea.2019`. \n",
    "* Furthermore, while the diffusion process gradually adds random noise to data samples, *diffusion models* :cite:`sohl2015deep,ho2020denoising` learn the denoising process to gradually construct data samples from random noise, reversing the diffusion process. They have started to replace generative adversarial networks in more recent deep generative models, such as in DALL-E 2 :cite:`ramesh2022hierarchical` and Imagen :cite:`saharia2022photorealistic` for creative art and image generation based on text descriptions.\n",
    "* In many cases, a single GPU is insufficient for processing the large amounts of data available for training.\n",
    "  Over the past decade the ability to build parallel and\n",
    "  distributed training algorithms has improved significantly.\n",
    "  One of the key challenges in designing scalable algorithms\n",
    "  is that the workhorse of deep learning optimization,\n",
    "  stochastic gradient descent, relies on relatively\n",
    "  small minibatches of data to be processed.\n",
    "  At the same time, small batches limit the efficiency of GPUs.\n",
    "  Hence, training on 1,024 GPUs with a minibatch size of,\n",
    "  say, 32 images per batch amounts to an aggregate minibatch\n",
    "  of about 32,000 images. Work, first by :citet:`Li.2017`\n",
    "  and subsequently by :citet:`You.Gitman.Ginsburg.2017`\n",
    "  and :citet:`Jia.Song.He.ea.2018` pushed the size up to 64,000 observations,\n",
    "  reducing training time for the ResNet-50 model\n",
    "  on the ImageNet dataset to less than 7 minutes.\n",
    "  By comparison, training times were initially of the order of days.\n",
    "* The ability to parallelize computation\n",
    "  has also contributed to progress in *reinforcement learning*.\n",
    "  This has led to significant progress in computers achieving\n",
    "  superhuman performance on tasks like Go, Atari games,\n",
    "  Starcraft, and in physics simulations (e.g., using MuJoCo)\n",
    "  where environment simulators are available.\n",
    "  See, e.g., :citet:`Silver.Huang.Maddison.ea.2016` for a description\n",
    "  of such achievements in AlphaGo. In a nutshell,\n",
    "  reinforcement learning works best\n",
    "  if plenty of (state, action, reward) tuples are available.\n",
    "  Simulation provides such an avenue.\n",
    "* Deep learning frameworks have played a crucial role\n",
    "  in disseminating ideas.\n",
    "  The first generation of open-source frameworks\n",
    "  for neural network modeling consisted of\n",
    "  [Caffe](https://github.com/BVLC/caffe),\n",
    "  [Torch](https://github.com/torch), and\n",
    "  [Theano](https://github.com/Theano/Theano).\n",
    "  Many seminal papers were written using these tools.\n",
    "  These have now been superseded by\n",
    "  [TensorFlow](https://github.com/tensorflow/tensorflow) (often used via its high-level API [Keras](https://github.com/keras-team/keras)), [CNTK](https://github.com/Microsoft/CNTK), [Caffe 2](https://github.com/caffe2/caffe2), and [Apache MXNet](https://github.com/apache/incubator-mxnet).\n",
    "  The third generation of frameworks consists\n",
    "  of so-called *imperative* tools for deep learning,\n",
    "  a trend that was arguably ignited by [Chainer](https://github.com/chainer/chainer),\n",
    "  which used a syntax similar to Python NumPy to describe models.\n",
    "  This idea was adopted by both [PyTorch](https://github.com/pytorch/pytorch),\n",
    "  the [Gluon API](https://github.com/apache/incubator-mxnet) of MXNet,\n",
    "  and [JAX](https://github.com/google/jax).\n",
    "\n",
    "\n",
    "The division of labor between system researchers building better tools\n",
    "and statistical modelers building better neural networks\n",
    "has greatly simplified things. For instance,\n",
    "training a linear logistic regression model\n",
    "used to be a nontrivial homework problem,\n",
    "worthy to give to new machine learning\n",
    "Ph.D. students at Carnegie Mellon University in 2014.\n",
    "By now, this task can be accomplished\n",
    "with under 10 lines of code,\n",
    "putting it firmly within the reach of any programmer.\n",
    "\n",
    "\n",
    "## Success Stories\n",
    "\n",
    "Artificial intelligence has a long history of delivering results\n",
    "that would be difficult to accomplish otherwise.\n",
    "For instance, mail sorting systems\n",
    "using optical character recognition\n",
    "have been deployed since the 1990s.\n",
    "This is, after all, the source\n",
    "of the famous MNIST dataset\n",
    "of handwritten digits.\n",
    "The same applies to reading checks for bank deposits and scoring\n",
    "creditworthiness of applicants.\n",
    "Financial transactions are checked for fraud automatically.\n",
    "This forms the backbone of many e-commerce payment systems,\n",
    "such as PayPal, Stripe, AliPay, WeChat, Apple, Visa, and MasterCard.\n",
    "Computer programs for chess have been competitive for decades.\n",
    "Machine learning feeds search, recommendation, personalization,\n",
    "and ranking on the Internet.\n",
    "In other words, machine learning is pervasive, albeit often hidden from sight.\n",
    "\n",
    "It is only recently that AI\n",
    "has been in the limelight, mostly due to\n",
    "solutions to problems\n",
    "that were considered intractable previously\n",
    "and that are directly related to consumers.\n",
    "Many of such advances are attributed to deep learning.\n",
    "\n",
    "* Intelligent assistants, such as Apple's Siri,\n",
    "  Amazon's Alexa, and Google's assistant,\n",
    "  are able to respond to spoken requests\n",
    "  with a reasonable degree of accuracy.\n",
    "  This includes menial jobs, like turning on light switches,\n",
    "  and more complex tasks, such as arranging barber's appointments\n",
    "  and offering phone support dialog.\n",
    "  This is likely the most noticeable sign\n",
    "  that AI is affecting our lives.\n",
    "* A key ingredient in digital assistants\n",
    "  is their ability to recognize speech accurately.\n",
    "  The accuracy of such systems has gradually\n",
    "  increased to the point\n",
    "  of achieving parity with humans\n",
    "  for certain applications :cite:`Xiong.Wu.Alleva.ea.2018`.\n",
    "* Object recognition has likewise come a long way.\n",
    "  Identifying the object in a picture\n",
    "  was a fairly challenging task in 2010.\n",
    "  On the ImageNet benchmark researchers from NEC Labs\n",
    "  and University of Illinois at Urbana-Champaign\n",
    "  achieved a top-five error rate of 28% :cite:`Lin.Lv.Zhu.ea.2010`.\n",
    "  By 2017, this error rate was reduced to 2.25% :cite:`Hu.Shen.Sun.2018`.\n",
    "  Similarly, stunning results have been achieved\n",
    "  for identifying birdsong and for diagnosing skin cancer.\n",
    "* Prowess in games used to provide\n",
    "  a measuring stick for human ability.\n",
    "  Starting from TD-Gammon, a program for playing backgammon\n",
    "  using temporal difference reinforcement learning,\n",
    "  algorithmic and computational progress\n",
    "  has led to algorithms for a wide range of applications.\n",
    "  Compared with backgammon, chess has\n",
    "  a much more complex state space and set of actions.\n",
    "  DeepBlue beat Garry Kasparov using massive parallelism,\n",
    "  special-purpose hardware and efficient search\n",
    "  through the game tree :cite:`Campbell.Hoane-Jr.Hsu.2002`.\n",
    "  Go is more difficult still, due to its huge state space.\n",
    "  AlphaGo reached human parity in 2015,\n",
    "  using deep learning combined with Monte Carlo tree sampling :cite:`Silver.Huang.Maddison.ea.2016`.\n",
    "  The challenge in Poker was that the state space is large\n",
    "  and only partially observed\n",
    "  (we do not know the opponents' cards).\n",
    "  Libratus exceeded human performance in Poker\n",
    "  using efficiently structured strategies :cite:`Brown.Sandholm.2017`.\n",
    "* Another indication of progress in AI\n",
    "  is the advent of self-driving vehicles.\n",
    "  While full autonomy is not yet within reach,\n",
    "  excellent progress has been made in this direction,\n",
    "  with companies such as Tesla, NVIDIA,\n",
    "  and Waymo shipping products\n",
    "  that enable partial autonomy.\n",
    "  What makes full autonomy so challenging\n",
    "  is that proper driving requires\n",
    "  the ability to perceive, to reason\n",
    "  and to incorporate rules into a system.\n",
    "  At present, deep learning is used primarily\n",
    "  in the visual aspect of these problems.\n",
    "  The rest is heavily tuned by engineers.\n",
    "\n",
    "\n",
    "\n",
    "This barely scratches the surface\n",
    "of significant applications of machine learning.\n",
    "For instance, robotics, logistics, computational biology,\n",
    "particle physics, and astronomy\n",
    "owe some of their most impressive recent advances\n",
    "at least in parts to machine learning, which is thus becoming\n",
    "a ubiquitous tool for engineers and scientists.\n",
    "\n",
    "Frequently, questions about a coming AI apocalypse\n",
    "and the plausibility of a *singularity*\n",
    "have been raised in non-technical articles.\n",
    "The fear is that somehow machine learning systems\n",
    "will become sentient and make decisions,\n",
    "independently of their programmers,\n",
    "that directly impact the lives of humans.\n",
    "To some extent, AI already affects\n",
    "the livelihood of humans in direct ways:\n",
    "creditworthiness is assessed automatically,\n",
    "autopilots mostly navigate vehicles, decisions about\n",
    "whether to grant bail use statistical data as input.\n",
    "More frivolously, we can ask Alexa to switch on the coffee machine.\n",
    "\n",
    "Fortunately, we are far from a sentient AI system\n",
    "that could deliberately manipulate its human creators.\n",
    "First, AI systems are engineered,\n",
    "trained, and deployed\n",
    "in a specific, goal-oriented manner.\n",
    "While their behavior might give the illusion\n",
    "of general intelligence, it is a combination of rules, heuristics\n",
    "and statistical models that underlie the design.\n",
    "Second, at present, there are simply no tools for *artificial general intelligence*\n",
    "that are able to improve themselves,\n",
    "reason about themselves, and that are able to modify,\n",
    "extend, and improve their own architecture\n",
    "while trying to solve general tasks.\n",
    "\n",
    "A much more pressing concern is how AI is being used in our daily lives.\n",
    "It is likely that many routine tasks, currently fulfilled by humans, can and will be automated.\n",
    "Farm robots will likely reduce the costs for organic farmers\n",
    "but they will also automate harvesting operations.\n",
    "This phase of the industrial revolution\n",
    "may have profound consequences for large swaths of society,\n",
    "since menial jobs provide much employment \n",
    "in many countries.\n",
    "Furthermore, statistical models, when applied without care,\n",
    "can lead to racial, gender, or age bias and raise\n",
    "reasonable concerns about procedural fairness\n",
    "if automated to drive consequential decisions.\n",
    "It is important to ensure that these algorithms are used with care.\n",
    "With what we know today, this strikes us as a much more pressing concern\n",
    "than the potential of malevolent superintelligence for destroying humanity.\n",
    "\n",
    "\n",
    "## The Essence of Deep Learning\n",
    "\n",
    "Thus far, we have talked in broad terms about machine learning.\n",
    "Deep learning is the subset of machine learning\n",
    "concerned with models based on many-layered neural networks.\n",
    "It is *deep* in precisely the sense that its models\n",
    "learn many *layers* of transformations.\n",
    "While this might sound narrow,\n",
    "deep learning has given rise\n",
    "to a dizzying array of models, techniques,\n",
    "problem formulations, and applications.\n",
    "Many intuitions have been developed\n",
    "to explain the benefits of depth.\n",
    "Arguably, all machine learning\n",
    "has many layers of computation,\n",
    "the first consisting of feature processing steps.\n",
    "What differentiates deep learning is that\n",
    "the operations learned at each of the many layers\n",
    "of representations are learned jointly from data.\n",
    "\n",
    "The problems that we have discussed so far,\n",
    "such as learning from the raw audio signal,\n",
    "the raw pixel values of images,\n",
    "or mapping between sentences of arbitrary lengths and\n",
    "their counterparts in foreign languages,\n",
    "are those where deep learning excels\n",
    "and traditional methods falter.\n",
    "It turns out that these many-layered models\n",
    "are capable of addressing low-level perceptual data\n",
    "in a way that previous tools could not.\n",
    "Arguably the most significant commonality\n",
    "in deep learning methods is *end-to-end training*.\n",
    "That is, rather than assembling a system\n",
    "based on components that are individually tuned,\n",
    "one builds the system and then tunes their performance jointly.\n",
    "For instance, in computer vision scientists\n",
    "used to separate the process of *feature engineering*\n",
    "from the process of building machine learning models.\n",
    "The Canny edge detector :cite:`Canny.1987`\n",
    "and Lowe's SIFT feature extractor :cite:`Lowe.2004`\n",
    "reigned supreme for over a decade as algorithms\n",
    "for mapping images into feature vectors.\n",
    "In bygone days, the crucial part of applying machine learning to these problems\n",
    "consisted of coming up with manually-engineered ways\n",
    "of transforming the data into some form amenable to shallow models.\n",
    "Unfortunately, there is only so much that humans can accomplish\n",
    "by ingenuity in comparison with a consistent evaluation\n",
    "over millions of choices carried out automatically by an algorithm.\n",
    "When deep learning took over,\n",
    "these feature extractors were replaced\n",
    "by automatically tuned filters that yielded superior accuracy.\n",
    "\n",
    "Thus, one key advantage of deep learning is that it replaces\n",
    "not only the shallow models at the end of traditional learning pipelines,\n",
    "but also the labor-intensive process of feature engineering.\n",
    "Moreover, by replacing much of the domain-specific preprocessing,\n",
    "deep learning has eliminated many of the boundaries\n",
    "that previously separated computer vision, speech recognition,\n",
    "natural language processing, medical informatics, and other application areas,\n",
    "thereby offering a unified set of tools for tackling diverse problems.\n",
    "\n",
    "Beyond end-to-end training, we are experiencing a transition\n",
    "from parametric statistical descriptions to fully nonparametric models.\n",
    "When data is scarce, one needs to rely on simplifying assumptions about reality\n",
    "in order to obtain useful models.\n",
    "When data is abundant, these can be replaced\n",
    "by nonparametric models that better fit the data.\n",
    "To some extent, this mirrors the progress\n",
    "that physics experienced in the middle of the previous century\n",
    "with the availability of computers.\n",
    "Rather than solving by hand parametric approximations of how electrons behave,\n",
    "one can now resort to numerical simulations of the associated partial differential equations.\n",
    "This has led to much more accurate models,\n",
    "albeit often at the expense of interpretation.\n",
    "\n",
    "Another difference from previous work is the acceptance of suboptimal solutions,\n",
    "dealing with nonconvex nonlinear optimization problems,\n",
    "and the willingness to try things before proving them.\n",
    "This new-found empiricism in dealing with statistical problems,\n",
    "combined with a rapid influx of talent has led\n",
    "to rapid progress in the development of practical algorithms,\n",
    "albeit in many cases at the expense of modifying\n",
    "and re-inventing tools that existed for decades.\n",
    "\n",
    "In the end, the deep learning community prides itself\n",
    "on sharing tools across academic and corporate boundaries,\n",
    "releasing many excellent libraries, statistical models,\n",
    "and trained networks as open source.\n",
    "It is in this spirit that the notebooks forming this book\n",
    "are freely available for distribution and use.\n",
    "We have worked hard to lower the barriers of access\n",
    "for anyone wishing to learn about deep learning\n",
    "and we hope that our readers will benefit from this.\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "Machine learning studies how computer systems\n",
    "can leverage experience (often data)\n",
    "to improve performance at specific tasks.\n",
    "It combines ideas from statistics, data mining, and optimization.\n",
    "Often, it is used as a means of implementing AI solutions.\n",
    "As a class of machine learning, representational learning\n",
    "focuses on how to automatically find\n",
    "the appropriate way to represent data.\n",
    "Considered as multi-level representation learning\n",
    "through learning many layers of transformations,\n",
    "deep learning replaces not only the shallow models\n",
    "at the end of traditional machine learning pipelines,\n",
    "but also the labor-intensive process of feature engineering.\n",
    "Much of the recent progress in deep learning\n",
    "has been triggered by an abundance of data\n",
    "arising from cheap sensors and Internet-scale applications,\n",
    "and by significant progress in computation, mostly through GPUs.\n",
    "Furthermore, the availability of efficient deep learning frameworks\n",
    "has made design and implementation of whole system optimization significantly easier,\n",
    "and this is a key component in obtaining high performance.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Which parts of code that you are currently writing could be \"learned\",\n",
    "   i.e., improved by learning and automatically determining design choices\n",
    "   that are made in your code?\n",
    "   Does your code include heuristic design choices?\n",
    "   What data might you need to learn the desired behavior?\n",
    "1. Which problems that you encounter have many examples for their solution,\n",
    "   yet no specific way for automating them?\n",
    "   These may be prime candidates for using deep learning.\n",
    "1. Describe the relationships between algorithms, data, and computation. How do characteristics of the data and the current available computational resources influence the appropriateness of various algorithms?\n",
    "1. Name some settings where end-to-end training is not currently the default approach but where it might be useful.\n",
    "\n",
    "[Discussions](https://discuss.d2l.ai/t/22)\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "required_libs": []
 },
 "nbformat": 4,
 "nbformat_minor": 5
}